首页 题解

# Description

Luogu传送门

# Solution

偶然发现这道题所以来做做。

刚开始看完题的时候感觉这只能暴力模拟……

于是不要脸的看了一眼题解之后，我们可以用一些表达式来表示每头奶牛到达它应该到的位置的时间，从而计算出总共时间。

具体来说，第 nn 头牛到达其位置所用时间是 sn+tns_n + t_n，第 n−1n - 1 头牛到达 sns_n 的时间就是 sn+tn+1s_n + t_n + 1（因为 cown−1cow_{n - 1} 初始坐标比 cowncow_n 的坐标靠左 1）

所以我们可以用二元组 (posi,timei)(pos_i, time_i) 来表示一头牛到达 posipos_i 所花的时间为 timeitime_i，对于一头牛有许多这样的二元组来限制它。

那么这只牛走到目的地的时间就是 max⁡{timei+(S−posi)}+T\max\{time_i + (S - pos_i)\} + T，二元组满足条件 posi≤Spos_i \leq S。

我们再把 SS 提出来，所以要找的就是 timei−positime_i - pos_i 的最大值。

但是目前复杂度还是 n2n^2 的，我们还要考虑如何优化。

不难发现，对于两个二元组限制条件 (a,b)(a, b) 和 (c,d)(c, d)，如果 a<ca < c 且 d−c<b−ad - c < b - a，那么 (c,d)(c, d) 对于以后所有的奶牛都是没有用的。

d−c<b−ad - c < b - a 使得 (c,d)(c, d) 对于当前的奶牛没有贡献，再加上 a<ca < c 使得 (c,d)(c, d) 这个条件对于后面所有的奶牛都没有了贡献。

所以我们直接把这个条件删掉即可。

用平衡树维护一下 pospos 和 time−postime - pos 的值，以及 time−postime - pos 的最大值，倒序枚举每一头奶牛：

  • 查询：把 pos≤Sipos \leq S_i 的数切下来查询。
  • 修改：当前插入的二元组是 (a,b)(a, b)，然后把树中 d−c>b−ad - c > b - a 的点全都删掉。

然后就没别的了，具体见代码吧。

我写的 fhq-treap

# Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <bits/stdc++.h>

using namespace std;

namespace IO{
    inline int read(){
        int x = 0;
        char ch = getchar();
        while(!isdigit(ch)) ch = getchar();
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x;
    }

    template <typename T> inline void write(T x){
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;

const int N = 2e5 + 10;
int n;
int S[N], T[N];

namespace FHQ_treap{
    #define ls(x) t[x].l
    #define rs(x) t[x].r

    struct tree{
        int sum, wei, l, r, x, y, val, tag;
    }t[N];
    int root, tot;

    inline void pushup(int x){
        if(!x) return;
        t[x].val = t[x].y;
        if(ls(x)) t[x].val = max(t[x].val, t[ls(x)].val);
        if(rs(x)) t[x].val = max(t[x].val, t[rs(x)].val);
    }

    inline void pushdown(int x){
        if(!x || !t[x].tag) return;
        int tag = t[x].tag;
        if(ls(x)){
            t[ls(x)].x -= tag, t[ls(x)].y += tag;
            t[ls(x)].tag += tag, t[ls(x)].val += tag;
        }
        if(rs(x)){
            t[rs(x)].x -= tag, t[rs(x)].y += tag;
            t[rs(x)].tag += tag, t[rs(x)].val += tag;
        }
        t[x].tag = 0;
    }

    inline void split_pos(int x, int k, int &a, int &b){
        if(!x) return a = b = 0, void();
        pushdown(x);
        if(k >= t[x].x) a = x, split_pos(rs(x), k, rs(x), b);
        else b = x, split_pos(ls(x), k, a, ls(x));
        pushup(x);
    }

    inline void split_val(int x, int k, int &a, int &b){
        if(!x) return a = b = 0, void();
        pushdown(x);
        if(k >= t[x].y) a = x, split_val(rs(x), k, rs(x), b);
        else b = x, split_val(ls(x), k, a, ls(x));
        pushup(x);
    }

    inline int merge(int x, int y){
        if(!x || !y) return x | y;
        if(t[x].wei <= t[y].wei){
            pushdown(x);
            rs(x) = merge(rs(x), y);
            return pushup(x), x;
        }else{
            pushdown(y);
            ls(y) = merge(x, ls(y));
            return pushup(y), y;
        }
    }

    inline int newnode(int a, int b){
        t[++tot].x = a, t[tot].y = t[tot].val = b, t[tot].wei = rand();
        return tot;
    }
}
using namespace FHQ_treap;

int main(){
    n = read();
    for(int i = 1; i <= n; ++i)
        S[i] = read(), T[i] = read();
    int ans = 0, a, b, c;
    root = newnode(0, 0);
    for(int i = n; i >= 1; --i){
        split_pos(root, S[i], a, b);
        int res = t[a].val + S[i] + T[i];
        ans = max(ans, res);
        t[a].tag++, t[a].x--, t[a].y++, t[a].val++;//奶牛初始坐标向左依次减 1，对于 (a, b) 来说相当于变成了 (a - 1, b)
        split_val(b, res + 1 - S[i], b, c);
        root = merge(a, merge(newnode(S[i], res + 1 - S[i]), c));
    }
    write(ans), puts("");
    return 0;
}

_EOF_\_EOF\_